package Offer82;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 含有重复元素集合的组合
 * 给定一个可能有重复数字的整数数组candidates和一个目标数target，
 * 找出candidates中所有可以使数字和为target的组合。
 * candidates中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
 *
 * @author 23737
 * @time 2021.11.16
 */
public class Test {
    public static void main(String[] args) {

    }
}

/**
 * 使用dfs回溯
 */
class Solution {
    public List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length == 0) {
            return list;
        }
        List<Integer> list1 = new ArrayList<>();
        dfs(list1, target, candidates, 0);
        return list;
    }

    //dfs回溯
    private void dfs(List<Integer> list1, int target, int[] candidates, int i) {
        if(target < 0){
            return;
        }
        if(target == 0){
            List<Integer> li = new ArrayList<>(list1);
            Collections.sort(li);
            if(!list.contains(li)){
                list.add(li);
            }
            return;
        }
        for (int j = i; j < candidates.length; j++) {
            list1.add(candidates[j]);
            dfs(list1,target-candidates[j],candidates,j+1);
            list1.remove(list1.size()-1);
        }
    }
}
